package com.darrenchan.leetcode;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-01-27 02:32
 */
public class QLint437 {
    //k个人，复印n本书
    public int copyBooks(int[] pages, int K) {
        if (pages == null || pages.length == 0) {
            return 0;
        }
        int n = pages.length;
        int[][] dp = new int[K + 1][n + 1];
        if(K > n) {
            K = n;
        }

        //init
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            dp[0][i] = Integer.MAX_VALUE;
        }

        for (int k = 1; k <= K; k++) {
            for (int i = 0; i <= n; i++) {
                dp[k][i] = Integer.MAX_VALUE;
                int sum = 0;
                for (int j = i; j >= 0; j--) {
                    dp[k][i] = Math.min(dp[k][i], Math.max(dp[k - 1][j], sum));
                    if(j > 0){
                        sum += pages[j - 1];
                    }
                }
            }
        }

        return dp[K][n];
    }
}
